#include <stdio.h>
#include <stdlib.h>

int F[11] = { 0, 1, 1, 2, 3, 5, 8,13,21,34,55};

int Fibonacci_Search(int *a, int n, int key)
{
	int low, high, mid, i, k;
	low = 1;
	high = n;
	k = 0;
	while(n > F[k]-1)
		k++;
	for (i = n; i < F[k]-1; ++i)
		a[i] = a[n];
	while(low <= high)
	{
		mid = low + F[k-1]-1;
		if (key < a[mid])
		{
			high = mid - 1;
			k = k - 1;
		}
		else if (key > a[mid])
		{
			low = mid + 1;
			k = k - 2;
		}
		else
		{
			if (mid <= n)
			{
				return mid;
			}
			else
				return n;
		}
	}
	return 0;
}

int main()
{
                //0  1  2  3  4  5  6  7  8  9 10
  //int F[11] = { 0, 1, 1, 2, 3, 5, 8,13,21,34,55};
    int a[11] = { 0, 1,16,24,35,47,59,62,73,88,99};
    int result;
    result = Fibonacci_Search(a, 10, 59);
    printf("%d\n",result);
    return 0;
}










